package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-postorder-traversal/">二叉树的后序遍历(Binary Tree Postorder Traversal)</a>
 * <p>给你一棵二叉树的根节点 root ，返回其节点值的<b>后序</b>遍历 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/binary-tree-inorder-traversal/'>示例</a>
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [0, 100] 内</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 * <b>进阶：递归算法很简单，你可以通过迭代算法完成吗？</b>
 *
 * @author c2b
 * @see LC0094BinaryTreeInorderTraversal_S 二叉树的中序遍历
 * @see LC0144BinaryTreePreorderTraversal_S 二叉树的前序遍历
 * @see LC0145BinaryTreePostorderTraversal_S 二叉树的后序遍历
 * @since 2023/5/12 10:20
 */
public class LC0145BinaryTreePostorderTraversal_S {
    static class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            return postorderTraversalByIteration(root);
            //return postorderTraversalByRecursion(root);
        }

        private List<Integer> postorderTraversalByIteration(TreeNode root) {
            List<Integer> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Deque<TreeNode> helper = new LinkedList<>();
            helper.addFirst(root);
            while (!helper.isEmpty()) {
                TreeNode currNode = helper.removeFirst();
                resList.add(0, currNode.val);
                if (currNode.left != null) {
                    helper.addFirst(currNode.left);
                }
                if (currNode.right != null) {
                    helper.addFirst(currNode.right);
                }
            }
            return resList;
        }

        private List<Integer> postorderTraversalByRecursion(TreeNode root) {
            List<Integer> resList = new ArrayList<>();
            postorderTraversalByRecursion(root, resList);
            return resList;
        }

        private void postorderTraversalByRecursion(TreeNode root, List<Integer> resList) {
            if (root == null) {
                return;
            }
            postorderTraversalByRecursion(root.left, resList);
            postorderTraversalByRecursion(root.right, resList);
            resList.add(root.val);
        }
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.right = new TreeNode(2);
        node.right.left = new TreeNode(3);

        Solution solution = new Solution();
        Printer.printListInteger(solution.postorderTraversal(node));
    }
}